package top.retain;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author ivorfan
 * @date 2021/8/2 16:22
 */
public class Fenge {

    public static void main(String[] args) {
        Fenge fenge = new Fenge();
        fenge.partition("aab");
    }
    // 回溯+动态规划。动态规划快速判断是否是回文串，回溯进行全排列。
    // dp[i][j] = true, i>=j; dp[i+1][j-1] && s[i] == s[j]
    List<List<String>> res = new ArrayList<>();
    public List<List<String>> partition(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], true);
        }
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                dp[i][j] = dp[i + 1][j - 1] && (s.charAt(i) == s.charAt(j));
            }
        }

        backTrack(s,0,n,new LinkedList<String>(),dp);
        return res;
    }

    private void backTrack(String s, int i, int n,LinkedList<String> track, boolean[][] dp) {
        if (i == n) {
            res.add(new ArrayList<>(track));
            return;
        }
        for (int j = i; j < n; j++) {
          if (isHuiWen(dp,i,j)) {
              track.add(s.substring(i,j+1));
              backTrack(s, j+1,n,track,dp);
              track.removeLast();
          }
        }

    }

    public boolean isHuiWen(boolean[][] dp, int i, int j) {
        return dp[i][j];
    }
}
